package com.whitedust.top10;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author A
 * @since 2025/11/1 14:41
 */

public class Top4 {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq2 = new PriorityQueue<>(nums.length);
        for (int num : nums) {
            pq2.offer(num);
        }
        for (int i = 0; i < nums.length - k; i++) {
            pq2.poll();
        }
        return pq2.peek();
    }
    public int findKthLargestPartition(int[] nums, int k) {
        List<Integer> list = Arrays.stream(nums).boxed().toList();
        return partitionFind(list, k);
    }
    private int partitionFind(List<Integer>nums,int k){
        Integer pivot = nums.get(0);
        List<Integer>low = new ArrayList<>();
        List<Integer>high = new ArrayList<>();
        List<Integer>equal = new ArrayList<>();
        for(int num:nums){
            if(num<pivot){
                low.add(num);
            }else if(num>pivot){
                high.add(num);
            }else{
                equal.add(num);
            }
        }
        if(k<=high.size()){
            return partitionFind(high,k);
        }else if(k<=high.size()+equal.size()){
            return pivot;
        }else{
            return partitionFind(low,k-high.size()-equal.size());
        }
    }
}
